package demo.java.util;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.stream.Stream;

/**
 * @see java.util.Collection
 * @see LinkedList
 * @see PriorityQueue
 * @see java.util.concurrent.LinkedBlockingQueue
 * @see java.util.concurrent.BlockingQueue
 * @see java.util.concurrent.ArrayBlockingQueue
 * @see java.util.concurrent.PriorityBlockingQueue
 * 
 */
public class QueueDemo {

    static Logger logger = LoggerFactory.getLogger(QueueDemo.class);

    /**
     * <li>offer(E e) 将指定元素插入此队列的尾部。
     * <li>poll() 获取并移除此队列的头，如果此队列为空，则返回 null。
     * <li>peek() 获取但不移除此队列的头；如果此队列为空，则返回 null
     * <li>remove(Object o) 从队列中移除指定元素的单个实例（如果存在）
     * <li>contains(Object o) 如果此队列包含指定元素，则返回 true
     */
    @Test
    public void queue() {
        Queue<String> queue = new LinkedList<>();
        String a = queue.poll();
    }

    /**
     * <li>boolean add(E e);入队一个元素，如果有空间则直接插入，并返回true；如果没有空间则抛出IllegalStateException
     * <li>boolean offer(E e);入队一个元素，如果有空间则直接插入，并返回true；如果没有空间返回false
     * <li>void put(E e) throws InterruptedException;入队一个元素，如果有空间则直接插入，如果没有空间则一直阻塞等待
     * <li>boolean offer(E e, long timeout, TimeUnit unit) ;入队一个元素，如果有空间则直接插入，并返回true；如果没有空间则等待timeout时间，插入失败则返回false
     * <li>
     * <li>E take() throws InterruptedException;出队一个元素，如果存在则直接出队，如果没有空间则一直阻塞等待
     * <li>E poll(long timeout, TimeUnit unit) throws InterruptedException;出队一个元素，如果存在则直接出队，如果没有空间则等待timeout时间，无元素则返回null
     * <li>int remainingCapacity();返回该队列剩余的容量（如果没有限制则返回Integer.MAX_VALUE）
     * <li>boolean remove(Object o);如果元素o在队列中存在，则从队列中删除
     * <li>public boolean contains(Object o);判断队列中是否存在元素o
     * <li>int drainTo(Collection<? super E> c);将队列中的所有元素出队，并添加到给定的集合c中，返回出队的元素数量
     * <li>int drainTo(Collection<? super E> c, int maxElements);将队列中的元素出队，限制数量maxElements个，并添加到给定的集合c中，返回出队的元素数量
     */
    public void blockingQueue() {
        BlockingQueue blockingQueue = new LinkedBlockingQueue();
    }

    @Test
    public void testLinkedBlockingQueue() {
        LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>(2);
        queue.offer(0);
        queue.add(0);
    }

    @Test
    public void linkedList() {
        LinkedList<Integer> queue = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0));
        Integer e = null;
        while ((e = queue.poll()) != null) {
            System.out.println(e);
        }
        queue = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0));
        queue.remove();
    }

    /**
     * <li>poll 如果没有数据会返回Null
     * <li>pollFirst 等价与 poll
     * <li>remove 如果没有数据会抛 NoSuchElementException 异常
     */
    @Test
    public void poll_remove() {
        LinkedList<Integer> queue = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0));
        Integer e = null;
        while ((e = queue.poll()) != null) {
            System.out.println(e);
        }

        queue = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0));
        while ((e = queue.pollFirst()) != null) {
            System.err.println(e);
        }

        queue.pollLast();

        queue = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 0));
        try {
            while ((e = queue.remove()) != null) {
                System.err.println(e);
            }
        } catch (NoSuchElementException exception) {
            exception.printStackTrace();
        }
    }

    /**
     * 如果我们要实现一个线程安全的队列有两种实现方式一种是使用阻塞算法，另一种是使用非阻塞算法。
     * 使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现， 而非阻塞的实现方式则可以使用循环CAS的方式来实现。
     * 如：线程安全队列ConcurrentLinkedQueue。
     * <p>
     * ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，采用了“wait－free”算法来实现。
     * ConcurrentLinkedQueue由head节点和tail节点组成，每个节点（Node）由节点元素（item）和指向下一个节点的引用(next)组成，
     * 节点与节点之间就是通过这个next关联起来， 从而组成一张链表结构的队列。默认情况下head节点存储的元素为空，tair节点等于head节点。
     * sun.misc.Unsafe.compareAndSwapObject();
     * <p>
     * ConcurrentLinkedQueue 的非阻塞算法实现可概括为下面 5 点：
     * 
     * <li>使用 CAS 原子指令来处理对数据的并发访问，这是非阻塞算法得以实现的基础。
     * <li>head/tail 并非总是指向队列的头 / 尾节点，也就是说允许队列处于不一致状态。 这个特性把入队 /
     * 出队时，原本需要一起原子化执行的两个步骤分离开来，从而缩小了入队 / 出队时需要原子化更新值的范围到唯一变量。这是非阻塞算法得以实现的关键。
     * <li>由于队列有时会处于不一致状态。为此，ConcurrentLinkedQueue 使用三个不变式来维护非阻塞算法的正确性。
     * <li>以批处理方式来更新 head/tail，从整体上减少入队 / 出队操作的开销。
     * <li>为了有利于垃圾收集，队列使用特有的 head 更新机制；为了确保从已删除节点向后遍历，可到达所有的非删除节点，队列使用了特有的向后推进策略。
     * 
     * TODO: 补充实现原理及底层结构
     */
    @Test
    public void concurrentLinkedQueue() {
        ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
        Stream.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 0).forEach(e -> {
            boolean ok = queue.offer(e);
            logger.info("offer return :{}", ok);
        });
        List<Integer> tmp = new ArrayList<>(queue.size() * 2);
        Integer msg;
        while ((msg = queue.poll()) != null) {
            tmp.add(msg);
        }
        logger.info("list = {}", tmp);
    }


}
